package com.zhengb.algorithmdemo.leetcode.tree;

/**
 * 给定一个二叉树，检查它是否是镜像对称的。
 * <p>
 * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
 * <p>
 * 1
 * / \
 * 2   2
 * / \ / \
 * 3  4 4  3
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 * <p>
 * 1
 * / \
 * 2   2
 * \   \
 * 3    3
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/symmetric-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author zhengbo
 * @date 2020/3/16
 */
public class SymmetricTree {

    /**
     * 是否是镜像树
     *
     * @param root1
     * @param root2
     * @return
     */
    private boolean areMirrorTree(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null) {
            return false;
        }

        if (root1.val != root2.val) {
            return false;
        }
        return areMirrorTree(root1.left, root2.right) && areMirrorTree(root1.right, root2.left);
    }

    /**
     * 解决思路 判断根节点的左子树和右子树是否是镜像树
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {

        if (root == null) {
            return false;
        }

        return areMirrorTree(root.left, root.right);
    }
}
